The present invention is directed, in general, to distributed databases and, more specifically, to a system and method for serializing lazy updates in a distributed database without requiring timestamps.
Database systems were first implemented at only a single database site. As the number of distributed applications requiring access to the database increased, the complexity, size and the time required to access the database systems also increased. Shortly thereafter, a single database site became unable to process all the information in a timely manner.
To correct this database processing problem, companies developed new database systems in which the database was replicated at different sites along a network. With the use of replicated databases, distributed applications were able to achieve a higher level of performance, reliability and availability. However, the higher level of performance came with a price.
Replicated databases improved performance, but management of the replicated data became vastly more complicated. Gigabytes of data are replicated in distributed data warehouses and various World Wide Web sites on the Internet. In telecom as well as data networks, network management applications require real-time dissemination of updates to replicas with strong consistency guarantees.
Two broad approaches have been developed to handle the problem of replica updates in a distributed database system, an eager protocol and a lazy protocol. The eager protocol updates all the replicas of an item as part of a single transaction. Thus, an eager protocol ensures that executions are serializable. However, a major disadvantage of an eager protocol""s algorithms is that the number of operations in the transaction increases with the degree of replication, and since deadlock probability is proportional to the fourth power of the transaction size, eager protocols are unlikely to scale beyond a small number of sites.
In contrast, the lazy protocol posts updates to replicas through independent transactions that are spawned by the original updating transaction after it commits. Thus, the effective size of a transaction is reduced and the overall performance of the system improves due to fewer deadlocks. However, transaction execution must be orchestrated carefully to ensure serializability across the entire distributed database.
Due to its superior performance benefits, a number of conventional database management programs (e.g., Sybase(copyright), Oracle(copyright), CA-OpenIngres(copyright)) provide support for updating via a lazy protocol. Specifically, these programs provide an option in which each transaction executes locally, and then is propagated asynchronously to replicas after it commits (the replicas at each site are updated in the context of a separate transaction). Since each transaction executes locally and independently, the systems do not require multi-site commit protocols (e.g., two-phase commit) which tend to introduce blocking and are thus not easily scalable.
A problem, however, with the lazy replication approaches of most conventional systems is that they can easily lead to non-serializable executions. For instance, it is possible for the same data item to be concurrently updated at two different sites, thus resulting in an update conflict. Currently, commercial systems use reconciliation rules (e.g., install the update with the later timestamp) to merge conflicting updates. These rules do not guarantee serializability, unless the updates are commutative. Therefore, what is needed in the art is a way to guarantee serializability of updates within a replicated database system.
To address the above-discussed deficiencies of the prior art, the present invention provides a system for, and method of, ensuring serialization of lazy updates in a distributed database described by a directed acyclic copy graph. In one embodiment, the system includes: (1) a forest construction module that creates a forest having trees and edges from the directed acyclic copy graph and (2) a propagation module, associated with the forest construction module, that employs the edges of the forest to propagate the lazy updates among replicas in the distributed database and ensure the serialization.
The present invention therefore introduces the broad concept of restructuring the copy graph describing the distributed database into a forest of trees, and then employing the edges of the forest to control propagation of updates through the distributed database. In this manner, serialization can be guaranteed in distributed databases described by directed acyclic copy graphs.
In one embodiment of the present invention, each of the trees comprises a node with exactly one parent. In a related embodiment, each of the trees further comprises a root having no parent.
In one embodiment of the present invention, the propagation module propagates the lazy updates without employing timestamps. While timestamps may be employed, the present invention does not require them to guarantee serialization of lazy updates.
In one embodiment of the present invention, the forest construction module arbitrarily selects a sink node of the forest. Alternatively, the forest construction module can select a sink node according to one or more predetermined rules. A sink node is a node in a directed acyclic copy graph that does not have a directed edge to another node in the directed acyclic copy graph.
In one embodiment of the present invention, the propagation module propagates transactions within a child tree of the forest only to selected children of the child tree. In a related embodiment, the propagation module propagates transactions sequentially along edges of the forest. The edges are the propagation paths from a source database site to destination database site within the forest.
In one embodiment of the present invention, a counterpart of the system is located at each replica of the distributed database. A replica is a site that comprises a copy of the whole database or a site that contains at least one element of the database. Alternatively, the system may be located at a single replica site, or at fewer than all sites.
The foregoing has outlined, rather broadly, preferred and alternative features of the present invention so that those skilled in the art may better understand the detailed description of the invention that follows. Additional features of the invention will be described hereinafter that form the subject of the claims of the invention. Those skilled in the art should appreciate that they can readily use the disclosed conception and specific embodiment as a basis for designing or modifying other structures for carrying out the same purposes of the present invention. Those skilled in the art should also realize that such equivalent constructions do not depart from the spirit and scope of the invention in its broadest form.